#include <iostream>
#include <algorithm>
#include <iterator>
using namespace std;

//sort N unique intergers in s[N] range from 1 to N
//TIME = O(N)
//SPACE = O(N)
int* unique_sort(int S[],int length)
{
  int* sort = new int[length]; //pointers can use subscript
  //allocation via new and/or malloc must use pointer, not array 
  for(int i = 0;i<length;i++)
    sort[S[i]-1] = S[i];
  return sort;
}

int main()
{
  int a[] = {1,10,3,4,2,6,8,7,5,9};

  int* b = unique_sort(a,10);

  copy(a,a+10,ostream_iterator<int>(cout," ") );
  cout<<endl;
  copy(b,b+10,ostream_iterator<int>(cout," ") );
  cout<<endl;

  free(b);
  return 0;
}
